package  
{
	import flash.utils.getTimer;
	/**
	 * ...
	 * @author 
	 */
	public class Astar 
	{
		private var map:Map;//地图
		private var open:Array;//开放列表
		private var close:Array;//关闭列表
		private var path:Array;//找到的路径
		private var cost:Number = 10;//水平、垂直方向的代价
		
		/**
		 * 初始化各种数据
		 */
		public function Astar(_map:Map) 
		{
			map = _map;
			open = new Array();
			close = new Array();
			map.startNode.g = 0;
			map.startNode.h = heuristic(map.startNode);
			map.startNode.f = map.startNode.g + map.startNode.h;
		}
		/**
		 * 估价函数 采用的是manhattan距离
		 * @param	node
		 * @return		node的h值
		 */
		private function heuristic(node:Node):Number
		{
			var horiz:Number = cost*Math.abs(node.col - map.endNode.col);
			var vert:Number = cost * Math.abs(node.row - map.endNode.row);
			return horiz + vert;
		}
		/**
		 * 寻路主函数
		 * @return 找到路径则返回true  否则 false
		 */
		public function findPath():Boolean
		{
			var currentNode:Node = map.startNode;//将起点作为当前节点，即将对它周围的节点进行计算
			while (currentNode != map.endNode)
			{
				//以下4个变量表示当前节点周围节点的row和col
				var startRow:uint = (currentNode.row - 1 >= 0)?currentNode.row - 1:0;
				var endRow:uint = (currentNode.row + 1 <= map.mapH-1)?currentNode.row + 1:map.mapH-1;
				var startCol:uint = (currentNode.col - 1 >= 0)?currentNode.col - 1:0;
				var endCol:uint = (currentNode.col + 1 <= map.mapW-1)?currentNode.col + 1:map.mapW-1;
				for (var i:uint = startRow; i <= endRow; i++ )
				{
					for (var j:uint = startCol; j <= endCol; j++ )//双重循环获取周围的节点
					{
						var testNode:Node = map.getNode(i, j);//将获取到的节点赋给一个变量(测试节点)
						if (testNode == currentNode || !testNode.isWalkAble
							|| !map.getNode(testNode.row, currentNode.col).isWalkAble
							|| !map.getNode(currentNode.row,testNode.col).isWalkAble)
						{
							continue;
						}
							if (testNode.col != currentNode.col && testNode.row != currentNode.row)
							{
								cost =14;
							}
							var g:Number= currentNode.g + cost;
							var h:Number= heuristic(testNode);
							var f:Number = g + h;
							if (isOpen(testNode) || isClose(testNode))
							{
								if (testNode.f > f)
								{
									testNode.f = f;
									testNode.g = g;
									testNode.h = h;
									testNode.parent = currentNode;
								}
							}
							else
							{
								testNode.f = f;
								testNode.g = g;
								testNode.h = h;
								testNode.parent = currentNode;
								open.push(testNode);
							}
					}
				}
				close.push(currentNode);
				if (open.length == 0)
				{
					trace("找不到路径");
					return false;
				}
				open.sortOn('f', Array.NUMERIC);
				currentNode=open.shift() as Node;
			}
			return true;
		}
		public function buildPath():Array
		{
			path = new Array();
			var node:Node = map.endNode;
			path.push(node);
			while (node != map.startNode)
			{
				node = node.parent;
				path.unshift(node);
			}
			return path;
		}
		private function isOpen(node:Node):Boolean
		{
			var len:int = open.length;
			for (var i:uint = 0; i < len; i++ )
			{
				if (node == open[i] as Node)
				{
					return true;
				}
			}
			return false;
		}
		private function isClose(node:Node):Boolean
		{
			var len:int = close.length;
			for (var i:uint = 0; i < len; i++ )
			{
				if (node == close[i] as Node)
				{
					return true;
				}
			}
			return false;
		}
		
	}

}